//一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出
//这个数字。 
//
// 
//
// 示例 1: 
//
// 输入: [0,1,3]
//输出: 2
// 
//
// 示例 2: 
//
// 输入: [0,1,2,3,4,5,6,7,9]
//输出: 8 
//
// 
//
// 限制： 
//
// 1 <= 数组长度 <= 10000 
//
// Related Topics 位运算 数组 哈希表 数学 二分查找 👍 394 👎 0


package leetcode.editor.cn;
class 缺失的数字{
    public static void main(String[] args) {
        Solution solution = new 缺失的数字().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        /**
         * 二分查找法
         * @param nums
         * @return
         */
    public int missingNumber1(int[] nums) {
        int length = nums.length;
        //返回的可能是缺少的数字前一位或者后一位
        int ans = binarySearch(nums,0,length -1);
        if(ans == nums[ans]){
            return ans + 1;
        }
        return ans;
    }
    
    public int binarySearch(int[] nums,int left,int right){
        if (left >= right) return left;
        int mid = left + ((right - left) >> 1);
        if (mid == nums[mid]){
            return binarySearch(nums, mid + 1,right);
        }
        return binarySearch(nums,left,mid - 1);
    }

        /**
         * 异或运算
         * @param nums
         * @return
         */
        public int missingNumber(int[] nums) {
            int length = nums.length;
            int xor = 0;
            for (int i = 0; i <= length - 1; i++) {
                xor ^= nums[i];
            }
            for (int i = 0; i <= length; i++) {
                xor ^= i;
            }
            
            return xor;
        }
}
//leetcode submit region end(Prohibit modification and deletion)

}

